Міністерство освіти і науки України Національний університет “Львівська політехніка” кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретна математика на тему: „Автомати з магазинною пам’яттю.” ЗМІСТ Анотація 3 Вступ 4 Базові означення МП-автоматів. 6 Варіанти МП-автоматів. 10 Еквівалентність МП-автоматів та КВ-мов. 15 Детерміновані МП-автомати. 22 Висновок 28 Список використаної літератури: 29 Додаток. 30 Анотація В даній курсовій роботі розглядаються автомати з магазинною пам’ятттю. Означення МП-автомата , а також варіанти МП-автоматів. Розглядається еквівалентність МП-автоматів і КВ-граматик. Також подано детерміновані МП-автомати , синтез МП-автомата. А в кінці програма реалізації синтезу ДМП-автомата. Вступ Теорія автоматів — логіко-математична теорія, об'єктом дослідження якої є абстрактні дискретні автомати — перервні перетворювачі інформації. Виникнення й розвиток теорії автоматів пов'язані з створенням технічних засобів автоматичного керування, проектуванням складних дискретних обчислюваних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо. Як цілісна конструктивна структурна теорія вона формується з поч. 50-х рр. 20 ст. Коло розв'язуваних теорією автоматів проблем велике: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування ЕОМ включно. У дискретній математиці, інформатиці, теорія автоматів вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати. Теорія автоматів найтісніше пов'язана з теорією алгоритмів. Це пояснюється тим, що автомат перетворить дискретну інформацію по кроках в дискретні моменти часу і формує результуючу інформацію по кроках заданого алгоритма. Ці перетворення можливі за допомогою технічних та/або програмних засобів. Автомат можна уявити як деякий пристрій (чорна скринька), на який подаються вхідні сигнали і знімаються вихідні, який до того ж може мати деякі внутрішні стани. Аналіз автоматів — знаходження за заданим в тому або іншому вигляді автоматові відображення «вхід — вихід», що здійснюється цим автоматом. Часто таке відображення можна інтерпретувати як обчислення предиката, і оскільки кожен предикат повністю характеризується своїм множиною істинності, то завдання аналізу автомата зводиться до знаходження цієї множини (говорять, що ця множина розпізнається автоматом). Для багатьох класів автоматів добре відомі класи розпізнаваних ними множин. Напр., Машини Тюринга розпізнають всі рекурсивні зліченні множини, автомати з магазинною пам'яттю (недетерміновані) — контекстні вільні мови, автомати скінченні — регулярні мови. Скінченні автомати можуть вирішувати лише ті завдання, які вимагають скінченого об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам’ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазина (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна вносити у магазин і видаляти їх з нього по одному. При цьому видаляється завжди лише верхній символ, тобто символ, який був внесений у магазин останнім. Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (МП–автомат). У ньому дуже просто поєднується пам’ять скінченого автомата і магазинна пам’ять. Отже, актуальним буде опрацювання питання про автомати з магазинною пам’яттю. Базові означення МП-автоматів. Автомат з магазинною пам’яттю—розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомат з магазинною пам’яттю—односторонній недетермінований розпізнавач , в потенційно нескінченній пам’яті якого елементи інформації зберігаються і вико...